This invention generally relates to video compression.
One of the most computation intensive functions in a video encoder system is the estimation of the translational motion (motion estimation) for each of the pixel blocks in a picture frame with respect to a previous or a future picture frame, in order to exploit the temporal redundancy in a frame sequence. The sole objective of motion estimation (ME) in video encoding is to exploit the temporal redundancy in a video sequence so as to improve the coding efficiency. The premise is that most of the objects in a scene move translationally across consecutive picture frames and hence, by locating the best matching pixel block in a previous or a future picture frame (reference frame), the information content of a block of pixels in a frame (target frame) can be coded by the pixel difference between the target block and the matching block, and the motion vector (MV), which is the relative location of the target and matching pixel blocks. This approach can substantially improve the coding efficiency of a video encoder system.
A straight-forward approach for ME is called full-search where all the pixel locations within a designated search range in the reference frame, centered around the location of the target block, are searched exhaustively for the best match. A commonly used best-matching criterion is minimum absolute difference (MAD), e.g., the sum of the absolute pixel-by-pixel difference (SAD) between the target block and the block at a matching location on the reference frame should be minimized. Although full-search ME produces high quality MVs, it requires prohibitively large amount of computations for video sequence of normal frame rate and size.
Hence, a more efficient ME algorithm is needed if a cost-effective video encoder system is to be built. The alternative motion estimation method of the invention is much more efficient than the full-search approach, yet produces close to full-search quality motion vectors. The present invention comprises a heuristic-based ME method. This ME method provides a substantial increase in speed over the full-search method, yet produces MVs that are close to the quality of a full-search.
The novel method includes: defining the target block; defining a simplified signature block; searching the reference frame using the simplified signature block; searching for the best match in the area centered around the location of the target block in the reference frame using the simplified signature; computing the sum of the absolute pixel-by-pixel difference using motion vectors obtained previously for the target block""s neighbors and the zero motion vector; selecting a new block with a motion vector with the minimum sum of the absolute pixel-by-pixel difference; and searching adjacent neighbors of the new block for minimum absolute difference match.